349. 两个数组的交集
349. 两个数组的交集
分析
其实我看到这个题目，我就想起来之前 242. 有效的字母异位词 中的做法，用字符的 ASCII 码作为数组下标，然后用数组来保存字符出现的次数，这个题目数组里面是数字，不是可以直接用数字做数组下标吗？可以是可以，但是如果数组中的数字的大小没有限制，那么我们就无法申请一个固定大小的数组，Java 中，int 的最大值是 2147483647 我们总不能申请一个长度为 2147483647 的数组吧，这样算法占用的空间会超，万幸，这个题的提示中限制了数组中数字的大小为 0 到 1000，因此我们用一个长度为 1001 的 int 数组保存即可。
说这么多的意思是什么呢？就是，使用数组来做哈希的题目，是因为题目都限制了 key 的大小，让 key 的 hash 结果长度有上限。 242 题，字符 hash 之后，结果长度为 26，这个题的数字 hash 之后的结果（就是本身）的长度为 1001，如果没有这些限制，就无法使用数组来做，就只能使用高级数据结构来做，在 Java 中，就是 Set<Integer> 了。
好了，接下来简单说一下思路。
首先用数组保存 nums1 中数字出现的次数，记住重复数字不重复累加次数，同样的操作对 nums2 也来一遍，然后对比两个统计结果数组，因为长度都是 1001，所以直接从头挨个开始对比每一个位置的数字，都不为 0，那就是重复数字，索引就是结果，然后这样全部遍历完，返回结果即可。
拓展：
如果题目没有限制数字的大小，应该怎么办，那就只能先对数组元素进行排序（升序排列），然后再用双指针法了，双指针法的做法也很简单，num1 的指针指向的数字为 number1 如果跟 num2 的指针指向的数字为 number2，直接开始比较，如果 number1 等于 number2，那么就直接放到结果里，这两个数字哪个小，就移动小数字所在数组指针。然后再次比较，直到一个数组遍历完。
解题
public int[] intersection(int[] nums1, int[] nums2) {
int shortLength = nums1.length>nums2.length?nums2.length:nums1.length;
int[] result = new int[shortLength];
int resultIndex =0;
int[] number1Count = new int[1001];
for(int i=0;i<nums1.length;i++){
int index = nums1[i];
// 重复数字不重复计算
if(number1Count[index]==0){
number1Count[index]++;
}
}
int[] number2Count = new int[1001];
for(int i=0;i<nums2.length;i++){
int index = nums2[i];
// 重复数字不重复计算
if(number2Count[index]==0){
number2Count[index]++;
}
}
for(int i=0;i<1001;i++){
if(number1Count[i]>0 && number2Count[i]>0){
result[resultIndex]=i;
resultIndex++;
}
}
int[] finalResult = new int[resultIndex];
for(int i=0;i<resultIndex;i++){
finalResult[i]=result[i];
}
return finalResult;
}